\section{Proofs for the two-hop walk}
\label{app:2hop}
\begin{LabeledProof}{Lemma~\ref{lem:mingrowth-1-10p}}
By the definition of $\md{0}$, $\dg{0}{w} \ge \md{0}$ for all
$w$ in $\nei{0}{1}{u}$.  Let $X$ be the first round at which
$|\nei{X}{2}{u}| \ge \md{0}/2$.  We consider two cases.  If $X$ is at
most $c n \log n$ for a constant $c$ to be specified later, then the
claim of the lemma holds.  In the remainder of this proof we consider
the case where $X$ is greater than $cn \log n$; thus, for $0 \le t \le
cn\log n$, $|\nei{t}{2}{u}| <\md{0}/2$.

Consider any node $w$ in $\nei{0}{1}{u}$.  Since $\dg{0}{w} \ge
\md{0}$ and $|\nei{t}{2}{u}| <\md{0}/2$, $w$ has at least $\md{0}/2$
edges to nodes in $\nei{0}{1}{u}$.  Fix a node $v$ in
$\nei{0}{2}{u}$.  In the following, we first show that in $O(n\log n)$
rounds, $v$ is strongly tied to the neighbors of $u$ with probability
at least $1-1/n^3$.  Let $T_1$ denote the first round at which $v$ has
is strongly tied to $\nei{T_1}{1}{u}$, i.e., when $|\nei{T_1}{1}{v}
\cap \nei{T_1}{1}{u}| \ge \md{0}/4$.  We know that $v$ has at least
one neighbor, say $w_1$, in $\nei{0}{1}{u}$.  Consider any $t < T_1$.
Since $v$ is weakly tied to $\nei{0}{1}{u}$ at time $t$, $w_1$ has at
least $\md{0}/4$ neighbors in $\nei{0}{1}{u}$ which do not have an
edge to $v$ at time $t$. This implies
\[\prob{v\mbox{ connects to a node in }\nei{0}{1}{u}\mbox{ through
  }w_1\mbox{ in round $t$}} \ge \frac{1}{n}\cdot\frac{1}{4} = \frac{1}{4n}\]

Let $e_1$ denote the event $\cub{v\mbox{ connects to a node in
  }\nei{0}{1}{u}}$, and $X_1$ be the number of rounds for $e_1$ to
occur.  When $e_1$ occurs, let $w_2$ denote a witness for $e_1$; i.e.,
$w_2$ is a node in $\nei{0}{1}{u}$ to which $v$ connects in round
$X_1$.  We note that $w_1,w_2\in \nei{0}{1}{u}\subseteq
\nei{X_1}{1}{u}$. If $v$ is weakly tied to $\nei{X_1}{1}{u}$, both
$w_1$ and $w_2$ have at least $\md{0}/4$ neighbors in
$\nei{X_1}{1}{u}$ that do not have an edge to $v$ yet. Let $e_2$
denote the event $\cub{v\mbox{ connects to a node in
  }\nei{X_1}{1}{u}}$, and $X_2$ be the number of rounds for $e_2$ to
occur. Then $\prob{e_2} = 2\prob{e_1} \ge 1/2n$.  Similarly, we define
$e_3,X_3,\dots, e_{\md{0}/4},X_{\md{0}/4}$ and obtain $\prob{e_i} \ge
i/(4n)$.  We now apply Lemma~\ref{lem:couponcorollary-10p} to obtain that
$X_1+X_2+\ldots X_{\md{0}/4}$ is at most $16n\ln n$ with probability
at least $1 - 1/n^3$.  Thus, with probability at least $1 -
|\nei{0}{2}{u}|/n^3$, $T_1 \le 16n \ln n$.  After $T_1$ rounds, we
obtain that for any $v \in \nei{0}{2}{u}$,
\[\prob{u\mbox{ connects to }v\mbox{ in a single round}} \ge \frac{\md{0}/4}{2\md{0}}\cdot\frac{1}{n} = \frac{1}{8n}.\]
which implies that with probability at least $1 - 1/n^3$, $u$ has an
edge to every node in $\nei{0}{2}{u}$ in another $T_2 \le 24 n \ln
n$ rounds.

Let $T_3$ equal $T_1 + T_2$; we set $c$ to be at least $120\ln 2$ so
that $X > 3T_3$.  We thus have $\nei{0}{2}{u}\subseteq
\nei{T_3}{1}{u}$, $\nei{0}{3}{u}\subseteq \nei{T_3}{1}{u}\cup
\nei{T_3}{2}{u}$, and $\nei{0}{4}{u}\subseteq \nei{T_3}{1}{u}\cup
\nei{T_3}{2}{u}\cup \nei{T_3}{3}{u}$. We now repeat the above analysis
again twice and obtain that at time $T = 3T_3$, $\nei{0}{2}{u}\cup
\nei{0}{3}{u}\cup \nei{0}{4}{u}\subseteq \nei{T}{1}{u}$ with
probability at least $1-\abs{\nei{0}{2}{u}\cup \nei{0}{3}{u}\cup
  \nei{0}{4}{u}}/n^3 \ge 1-1/n^2$.  By Lemma \ref{lem:moreneighbor-10p},
we have $\abs{\nei{T}{1}{u}}\ge \min\cub{2\md{0}, n-1}$, thus
completing the proof of the lemma.
\end{LabeledProof}

\begin{LabeledProof}{Lemma~\ref{lem:mingrowth-2-10p}}
Let $X$ be the first round at which $\nei{X}{2}{u} < \md{0}/4$. We
consider two cases. If $X$ is at most $cn\log n$ for a constant $c$ to
be specified later, then the claim of the lemma holds. In the
remainder of this proof we consider the case where $X$ is greater than
$cn\log n$; thus, for $0\le t\le cn\log n$, $\abs{\nei{t}{2}{u}} \ge
  \md{0}/4$. If $v\in \nei{0}{2}{u}$ is strongly tied to $\nei{0}{1}{u}$,
then
\[\prob{u\mbox{ connects to }v\mbox{ in a single round}} \ge
\frac{\dgi{t}{v}{\nei{0}{1}{u}}}{\abs{\nei{t}{1}{u}}}\cdot
\frac{1}{n}\ge \frac{\md{0}/4}{(1+1/8)\md{0}}\cdot \frac{1}{n} =
\frac{2}{9n}\] Thus, in $T = 13.5n\ln n$ rounds, $u$ will add an edge
to $v$ with probability at least $1-1/n^3$.  If there are at least
$\md{0}/8$ nodes in $\nei{0}{2}{u}$ that are strongly tied to
$\nei{0}{1}{u}$, then $u$ will add edges to all these nodes in $T$
rounds with probability at least $1-1/n^2$.

In the remainder of this proof, we focus on the case where the number
of nodes in $\nei{0}{2}{u}$ that are strongly tied to
$\nei{0}{1}{u}$ at the start of round $0$ is less than $\md{0}/8$.  In
this case, because $\abs{\nei{t}{2}{u}}\ge \md{0}/4$, more than
$\md{0}/8$ nodes in $\nei{0}{2}{u}$ are weakly tied to
$\nei{0}{1}{u}$, and, thus, have at least $3\md{0}/4$ edges to
nodes in $\nei{0}{2}{u}\cup \nei{0}{3}{u}$.

In the following we show $u$ will connect to $\md{0}/8$ nodes in
$O(n\log n)$ rounds with probability at least $1-1/n^2$.  For any
round $t$, let $W_t$ denote the set of nodes in $\nei{t}{2}{u}$
that are weakly tied to $\nei{t}{1}{u}$.  We refer to a length-2 path
from $u$ to a node two hops away as an {\em out-path}.  Let $P_0$
denote the set of out-paths to $W_0$.  Since we have at least
$\md{0}/8$ nodes in $\nei{0}{2}{u}$ that are weakly tied to
$\nei{0}{1}{u}$, $\abs{P_0}$ is at least $\md{0} /8$ at time
$t=0$. Define $e_1=\cub{u \mbox{ picks an out-path in $P_0$ and
    connects to node }v_1\mbox{ in }\nei{0}{2}{u}}$, and $X_1$ to be
the number of rounds for $e_1$ to occur.  When $0\le t\le X_1$, for
each $w_i\in \nei{t}{1}{u}$, let $f_i$ be the number of edges from
$w_i$ to nodes in $\nei{t}{1}{u}\cup \nei{t}{2}{u}$, and $p_i$ be
the number of edges from $w_i$ to nodes in $\nei{0}{2}{u}$ that are
weakly tied to $\nei{0}{1}{u}$.
\begin{eqnarray*}
\prob{e_1} 
&=& \sum_i \frac{1}{\dg{t}{u}} \cdot \frac{p_i}{f_i} 
\;\;\;\ge\;\;\; \sum_i \frac{1}{\dg{t}{u}} \cdot \frac{p_i}{n-1} 
\;\;\;=\;\;\; \frac{\sum_i p_i}{(1+1/8)\md{0}(n-1)} \\
&=& \frac{\abs{S}}{(1+1/8)\md{0}(n-1)} 
\;\;\;\ge\;\;\; \frac{\md{0}/8}{(1+1/8)\md{0}(n-1)} 
\;\;\;\ge\;\;\; \frac{1}{9n}.
\end{eqnarray*}
After $X_1$ rounds, $u$ will pick an out-path in $P_0$ and connect
such a $v_1$.  Define $P_1$ to be a set of out-paths from $u$ to
$W_{X_1}$.  We now place a lower bound on $|P_1 \setminus P_0|$.
Since $v_1\in \nei{0}{2}{u}$ is added to $\nei{X_1}{1}{u}$, those
out-paths in $P_0$ consisting of edges from $v_1$ to nodes in
$\nei{0}{1}{u}$ are not in $P_1$. The number of out-paths we lose
because of this is at most $\md{0}/4$.  But $v_1$ also has at least
$3\md{0}/4$ edges to $\nei{0}{2}{u}\cup \nei{0}{3}{u}$. The end points
of these edges are in $\nei{X_1}{1}{u}\cup \nei{X_1}{2}{u}$. If more
than $\md{0}/8$ of them are in $\nei{X_1}{1}{u}$, then $\dg{X_1}{u}\ge
(1+1/8)\md{0}$. Now let's consider the case that less than $\md{0}/8$
such end points are in $\nei{X_1}{1}{u}$. This means the number of
edges from $v_1$ to $\nei{X_1}{2}{u}$ is at least $3\md{0}/4 -
\md{0}/4 - \md{0}/8 = 3\md{0}/8$.  Among the end points of these
edges, if more than $\md{0}/8$ of them are strongly tied to
$\nei{X_1}{1}{u}$, then the degree of $u$ will become at least
$(1+1/8)\md{0}$ in $O(n \log n)$ rounds with probability $1-1/n^2$ by
our earlier argument. If not, we know that more than $\md{0}/4$ newly
added edges are pointing to nodes that are weakly tied to
$\nei{X_1}{1}{u}$.  Thus, $\abs{P_1 \setminus P_0}$ is by at least
$\md{0}/4$. $\abs{S} \ge 2\cdot \md{0}/8$. Define $e_2=\cub{u\mbox{
    picks an out-path in $P_1$ and connects to node }v_2}$, and $X_2$
to be the number of rounds for $e_2$ to occur. During time $X_1\le
t\le X_2$, $\prob{e_2}$ is at least $2\cdot\frac{1}{9n}$.  Similarly,
we define $e_3,X_3,\dots,e_{\md{0}/8},X_{\md{0}/8}$ and derive
$\prob{e_i} \ge i/(9n)$. By Lemma \ref{lem:couponcorollary-10p}, the
number of rounds for $\dg{t}{u}\ge (1+1/8)\md{0}$ is bounded by
\[T=X_1+X_2+\dots+X_{\md{0}/8} \le (2+1)9n\ln n = 27n\ln n\]
with probability at least $1-1/n^2$, completing the proof of this
lemma.
\end{LabeledProof}

\begin{LabeledProof}{Theorem~\ref{thm:graph+randwalk-10p}}
We first show that in time $T=O(n\log n)$ time, the minimum degree of
the graph increases by a factor of $1/8$, i.e., $\md{T} \ge
\min\cub{(1+1/8)\md{0}, n-1}$. Then we can apply this argument $O(\log n)$
times, and thus, complete the proof of this theorem.

For each $u$ where $\dg{0}{u} < \min\cub{(1+1/8)\md{0}, n-1}$, we
analyze by the following 2 cases. First, if $|\nei{0}{2}{u}| \ge \md{0}/2$, by Lemma
\ref{lem:mingrowth-2-10p} we know as long as $|\nei{t}{2}{u}|\ge \md{0}/4$
for all $t\ge 0$, $\dg{T}{u} \ge\min\cub{(1+1/8)\md{0},n-1}$ with
probability $1-1/n^2$ where $T=O(n\log n)$. Whenever the condition is
not satisfied, we know at least $\md{0}/4$ nodes in $\nei{0}{2}{u}$
has been moved to $\nei{T}{1}{u}$, which means $\dg{T}{u}
\ge\min\cub{(1+1/4)\md{0},n-1}$.

Second, if $|\nei{0}{2}{u}| < \md{0}/2$, by Lemma
\ref{lem:mingrowth-1-10p} we know as long as $|\nei{t}{2}{u}| < \md{0}/2$
for all $t\ge 0$, $\dg{T}{u} \ge\min\cub{(1+1/8)\md{0},n-1}$ with
probability $1-1/n^2$ where $T=O(n\log n)$. Whenever the condition is
not satisfied, we are back to the analysis in the first case, and the
minimum degree will become $\min\cub{(1+1/8)\md{0},n-1}$ with
probability $1-1/n^2$.

Combining the the above two cases we get that with
probability $1-1/n$ the minimum degree of $G$
will become at least $\min\cub{(1+1/8)\md{0},n-1}$ in $O(n\log n)$ rounds,
since there are at most $n$ nodes whose degree is between
$\md{0}$ and $\min\cub{(1+1/8)\md{0},n-1}$,

Now we can apply the above argument $O(\log n)$ times, and have shown
the two-hop walk process completes in $O(n\log^2 n)$ with high
probability. 
\end{LabeledProof}

